package com.clstu.recursion;

/**
 * 探究迷宫回溯问题  思考题:找到最短路径
 */
public class MiGong {
    private static int count = 0;
    public static void main(String[] args) {
        //用二维数组来表示迷宫,0没走过,1墙,2已经走过,3已经判断过走不通
        //创建迷宫地图
        int[][] map = creatMap();
        //查看开始的迷宫地图
        System.out.println("开始的地图如下:");
        for (int[] ints : map) {
            for (int i : ints) {
                System.out.print(i+"  ");
            }
            System.out.println();
        }
        //测试写的方法是否能够找到出路
//        if(findWay(map,1,1,1,2,3,4)){
//            System.out.println("找到的路如下:");
//            for (int[] ints : map) {
//                for (int i : ints) {
//                    System.out.print(i+"  ");
//                }
//                System.out.println();
//            }
//        }
        System.out.println("最短路径是:"+shortestLen());
        System.out.println("findWay()方法被递归调用了"+count+"次");
    }

//  含义:  0没走过,1墙,2已经走过,3已经判断过走不通
    //编写方法递归找到一条路线走到指定的地点,规定重点是[6][5],返回是否找到
    //map 表示地图,i,j表示当前自己的位置,a b c d表示走的顺序的方位,只能是(1下,2右,3上,4左)中的一个值,代表上下左右
    public static boolean findWay(int[][] map,int i,int j,int a,int b,int c,int d){
        //统计一下该方法被调用多少次
        count++;
        //如果最后到达了[6][5]位置
        if(map[6][5]==2){
            return true;
        }else {
            //先判断自己的坐标是否没走过
            if(map[i][j]==0){
                //先标记为走过
                map[i][j]=2;
                //再按照 1下--->2右--->3上--->4左 的顺序找出路
                switch (a){//第一个走的方向
                    case 1:
                        if(findWay(map,i+1,j,a,b,c,d)){//1下
                            return true;
                        }
                        break;
                    case 2:
                        if (findWay(map,i,j+1,a,b,c,d)){//2右
                            return true;
                        }
                        break;
                    case 3:
                        if (findWay(map,i-1,j,a,b,c,d)){//3上
                            return true;
                        }
                        break;
                    case 4:
                        if (findWay(map,i,j-1,a,b,c,d)){//4左
                            return true;
                        }
                        break;
                }
                switch (b){//第二个走的方向
                    case 1:
                        if (findWay(map, i + 1, j, a, b, c, d)) {//1下
                            return true;
                        }
                        break;
                    case 2:
                        if (findWay(map, i, j + 1, a, b, c, d)) {//2右
                            return true;
                        }
                        break;
                    case 3:
                        if (findWay(map, i - 1, j, a, b, c, d)) {//3上
                            return true;
                        }
                        break;
                    case 4:
                        if (findWay(map, i, j - 1, a, b, c, d)) {//4左
                            return true;
                        }
                        break;
                }
                switch (c){//第三个走的方向
                    case 1:
                        if(findWay(map,i+1,j,a,b,c,d)){//1下
                            return true;
                        }
                        break;
                    case 2:
                        if (findWay(map,i,j+1,a,b,c,d)){//2右
                            return true;
                        }
                        break;
                    case 3:
                        if (findWay(map,i-1,j,a,b,c,d)){//3上
                            return true;
                        }
                        break;
                    case 4:
                        if (findWay(map,i,j-1,a,b,c,d)){//4左
                            return true;
                        }
                        break;
                }
                switch (d){//第四个走的方向
                    case 1:
                        if(findWay(map,i+1,j,a,b,c,d)){//1下
                            return true;
                        }
                        break;
                    case 2:
                        if (findWay(map,i,j+1,a,b,c,d)){//2右
                            return true;
                        }
                        break;
                    case 3:
                        if (findWay(map,i-1,j,a,b,c,d)){//3上
                            return true;
                        }
                        break;
                    case 4:
                        if (findWay(map,i,j-1,a,b,c,d)){//4左
                            return true;
                        }
                        break;
                }
                //如果都没有找到出路,标记为死路,返回false
                map[i][j]=3;
                return false;
            }else {//如果该位置不能走(只有0没走过的位置可以走)
                return false;
            }
        }
    }

    //编写方法创建迷宫地图
    public static int[][] creatMap(){
        int[][] map = new int[8][7];
        //初始化墙
        for (int i = 0; i < 8; i++) {
            map[i][0]=1;
            map[i][6]=1;
        }
        for (int i = 0; i < 7; i++) {
            map[0][i]=1;
            map[7][i]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        return map;
    }

    //编写方法统计路径的长度,2的个数
    public static int wayLen(int[][] map){
        int count = 0;
        for (int[] ints : map) {
            for (int anInt : ints) {
                if (anInt==2) count++;
            }
        }
        return count;
    }

    //编写方法找到最短路径
    public static int shortestLen(){
        int cnt = 0;
        //将每一种种走路的策略都保存下来
        int[] lens = new int[24];
        for (int i = 1; i <=4 ; i++) {
            for (int j = 1; j <=4 ; j++) {
                for (int k = 1; k <=4 ; k++) {
                    for (int l = 1; l <=4 ; l++) {
                        //i j k l分别表示第1 2 3 4 次序判断的方向
                        if( i!=j && i!=k && i!=l && j!=k && j!=l &&k !=l ){
                            int[][] map = creatMap();
                            if (findWay(map,1,1,i,j,k,l)){
                                lens[cnt++] = wayLen(map);
                                System.out.println("找到第"+cnt+"次的路如下:");
                                for (int[] ints : map) {
                                    for (int n : ints) {
                                        System.out.print(n+"  ");
                                    }
                                    System.out.println();
                                }
                                System.out.println("长度:"+wayLen(map));
                            }else {
                                System.out.println("找不到可到达的路径,失败");
                            }
                        }
                    }
                }
            }
        }
        //较出最短的路径
        int shortest = lens[0];
        for (int len : lens) {
            if(shortest>len) shortest = len;
        }
        return shortest;
    }

}
